package com.cn.algorithm02.class22;

import com.sun.org.apache.regexp.internal.RE;

/***
 * @author: he_ls
 * @description: 5个参数 N,M,row,col,k
 *  给定5个参数，N，M，row，col k
 *  表示在N*M的区域上，醉汉Bob初始在(row,col)位置
 *  Bob一共要迈出k步，且每步都会等概率向上下左右四个方向走一个单位
 *  任何时候Bob只要离开N*M的区域，就直接死亡
 *  返回k步之后，Bob还在N*M的区域的概率
 *  象棋跳马问题
 *  空间压缩模型：   二维转一维    三维转二维
 *
 *  有枚举行为可以通过观察临近位置进行推理，无枚举则推理至傻缓存则就是最优解
 **/
public class C05_BobLive {

    /**
     * 一、暴力递归
     */
    public static double liveProbability(int N, int M, int row, int col, int k) {
        return (double) (process(N, M, row, col, k) / Math.pow(4, k));
    }

    private static long process(int N, int M, int row, int col, int rest) {
        if (row < 0 || row == N || col < 0 || col == M) {
            return 0;
        }
        if (rest == 0 /*&& row <= N - 1 && col <= M - 1*/) {
            return 1;
        }

        long left = process(N, M, row, col - 1, rest - 1);
        long right = process(N, M, row, col + 1, rest - 1);
        long up = process(N, M, row - 1, col, rest - 1);
        long down = process(N, M, row + 1, col, rest - 1);
        return left + right + up + down;
    }

    /**
     * 二、动态规划
     */
    public static double liveProbability2(int N, int M, int row, int col, int k) {
        long[][][] dp = new long[N][M][k + 1];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                dp[i][j][0] = 1;
            }
        }
        for (int rest = 1; rest <= k; rest++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    dp[i][j][rest] += pick(dp, N, M, i - 1, j, rest - 1);
                    dp[i][j][rest] += pick(dp, N, M, i + 1, j, rest - 1);
                    dp[i][j][rest] += pick(dp, N, M, i, j - 1, rest - 1);
                    dp[i][j][rest] += pick(dp, N, M, i , j + 1, rest - 1);
                }
            }
        }
        return (double) (dp[row][col][k]/ Math.pow(4, k));
    }

    public static long pick(long[][][] dp, int N, int M,int row, int col, int rest) {
        if (row < 0 || row == N || col < 0 || col == M) {
            return 0;
        }
        return dp[row][col][rest];
    }


    public static void main(String[] args) {
        int N = 6, M = 5;
        int row = 2, col = 3;
        int k = 10;
        System.out.println(liveProbability(N, M, row, col, k));
        System.out.println(liveProbability2(N, M, row, col, k));
    }
}
